In computing, computer systems may be made fault tolerant through replication. An approach to replication used in distributed systems is state machine replication. State machine replication involves replicating servers and coordinating client interactions with server replicas. For example, multiple state machines can form a set of replicated state machines (e.g., in some implementations, a replicated state library (“RSL”) ring) and propagate state updates amongst the state machines that are within the replicated state machine set (e.g., by employing the well-known Paxos algorithm or some other suitable algorithm for implementing a fault-tolerant distributed system). One state machine of the replicated state machine set may be selected as the primary state machine, and all state updates will be executed by the primary state machine and then propagated to the remaining state machines of the replicated state machine set. The remaining state machines of the replicated state machine set may be referred to as secondary state machines. In some implementations, a secondary state machine can implement the state update even if only a subset (e.g., a quorum) of the secondary state machines acknowledges the state update. Consequently, some of the secondary state machines of the replicated state machine set may be behind or out of date with respect to the other state machines.
Read requests for state data may be routed directly to and satisfied by secondary state machines of the replicated state machine set. This feature may be referred to as distributed reads. In some conventional implementations, distributed reads are implemented by having each client and state machine in the replicated state machine set maintain its own sequence number, wherein the sequence number is indicative of the most recent state of which that machine is aware. When a client sends a read request to the replicated state machine set, the client embeds in the read request the highest sequence number that the client has encountered. When a secondary state machine receives the read request, it will then compare its sequence number to the sequence number embedded in the read request. The secondary state machine services the read request only if its own sequence number is at least as high as the one in the read request, since in this case the secondary state machine is maintaining a state that is not behind (i.e., lagging) the state observed by the client. Otherwise, the secondary state machine redirects the request to the primary state machine.